An LDPC (low density parity check) code has high error correcting capability and recently, this begins to be widely adopted as a transmission scheme including digital satellite broadcasting such as DVB (digital video broadcasting)-S.2 used in Europe, for example (for example, refer to Non-Patent Document 1). Adoption of the LDPC code to next-generation digital terrestrial broadcasting is also considered.
Recent studies is proving that the LDPC code may obtain performance close to Shannon limit as a code length thereof is made longer as well as a turbo code and the like. The LDPC code characteristically has an advantage that a block error probability characteristic thereof is excellent and that a so-called error floor phenomenon observed in a decoding characteristic of the turbo code and the like scarcely occurs by its feature that a minimum distance is proportional to the code length.
Such LDPC code is hereinafter specifically described. Meanwhile, the LDPC code is a linear code and is not necessarily required to be a binary code; however, it is herein described supposing that this is the binary code.
The greatest characteristic of the LDPC code is that a parity check matrix defining the LDPC code is sparse. Herein, the sparse matrix is the matrix in which the number of elements “1” of the matrix is very small (most of elements are 0).
FIG. 1 illustrates an example of a parity check matrix H of the LDPC code.
In the parity check matrix H in FIG. 1, a weight of each column (column weight) (the number of “1”) is “3” and the weight of each row (row weight) is “6”.
In encoding by the LDPC code (LDPC encoding), a code word (LDPC code) is generated by generation of a generator matrix G based on the parity check matrix H and multiplication of the generator matrix G by a binary information bit, for example.
Specifically, an encoding device, which performs the LDPC encoding, first calculates the generator matrix G satisfying an equation GHT=0 between the same and a transposed matrix HT of the parity check matrix H. Herein, when the generator matrix is a K×N matrix, the encoding device multiplies a bit column (vector u) of K information bits by the generator matrix G to generate a code word c (=uG) composed of N bits. The code word (LDPC code) generated by the encoding device is received on a receiving side through a predetermined communication channel.
Decoding of the LDPC code may be performed by an algorithm suggested by Gallager as probabilistic decoding being a message passing algorithm by belief propagation on a so-called Tanner graph composed of a variable node (also referred to as a message node) and a check node. Hereinafter, the variable node and the check node are appropriately and simply referred to as a node.
FIG. 2 illustrates a procedure of the decoding of the LDPC code.
Meanwhile, a real value (received LLR) representing likelihood of a value to be “0” of an i-th code bit of the LDPC code (one cord word) received on the receiving side by a log likelihood ratio is hereinafter appropriately referred to as a received value u0i. A message output from the check node is set to uj and the message output from the variable node is set to vi.
First, in the decoding of the LDPC code, as illustrated in FIG. 2, the LDPC code is received, the message (check node message) uj is initialized to “0”, and a variable k being an integer as a counter of a repetitive process is initialized to “0” at step S11 and the procedure shifts to step S12. At step S12, the message (variable node message) vi is obtained by an operation (variable node operation) represented in equation (1) based on the received value u0i obtained by receiving the LDPC code and the message uj is obtained by an operation (check node operation) represented in equation (2) based on the message vi.
      [          Equation      ⁢                          ⁢      1        ]                                            v            i                    =                                    u                              0                ⁢                i                                      +                                          ∑                                  i                  =                  1                                                                      d                    v                                    -                  1                                            ⁢                                                          ⁢                                                u                  j                                ⁢                                                                  [                                  Equation                  ⁢                                                                          ⁢                  2                                ]                                                                          (          1          )                                                          tanh            ⁡                          (                                                u                  j                                2                            )                                =                                    Π                              i                =                1                                                              d                  o                                -                1                                      ⁢                          tanh              ⁡                              (                                                      v                    i                                    2                                )                                                                          (          2          )                    
Herein, dv and dc in equations (1) and (2) are parameters indicating the numbers of “1” in a vertical direction (column) and a horizontal direction (row) of the parity check matrix H, which may be optionally selected, and it is set that dv=3 and dc=6 in a case of a (3, 6) code, for example.
Meanwhile, in the variable node operation in equation (1) and the check node operation in equation (2), the message input from an edge (line connecting the variable node and the check node to each other) from which the message is to be output is not a target of the operation, so that a range of the operation is 1 to dv−1 or 1 to dc−1. Also, a table of a function R(v1, v2) represented in equation (3) defined by one output with respect to two inputs v1 and v2 is created in advance and this is continuously (recursively) used as represented in equation (4) for actually performing the check node operation in equation (2).[Equation 3]x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1,v2)   (3)[Equation 4]uj=R(v1,R(v2,R(v3, . . . R(vd0−2,vdc−1))))   (4)
At step S12, the variable k is incremented by 1 and the procedure shifts to step S13. At step S13, it is judged whether the variable k is larger than a predetermined number of times of repetitive decoding C. When it is judged that the variable k is not larger than C at step S13, the procedure returns to step S12 and a similar process is hereinafter repeatedly performed.
Also, when it is judged that the variable k is larger than C at step S13, the procedure shifts to step S14 to perform an operation represented in equation (5), so that the message vi as a decoding result to be finally output is obtained to be output and a decoding process of the LDPC code is finished.
      [          Equation      ⁢                          ⁢      5        ]                                            v            i                    =                                    u                              0                ⁢                i                                      +                                          ∑                                  j                  =                  1                                                  d                  y                                            ⁢                                                          ⁢                              u                j                                                                          (          5          )                    
Herein, different from the variable node operation in equation (1), the operation in equation (5) is performed using the messages uj from all the edges connected to the variable node.
FIG. 3 illustrates an example of the parity check matrix H of the (3, 6) LDPC code (code rate 1/2 and code length 12).
In the parity check matrix H in FIG. 3, the weight of the column is 3 and the weight of the row is 6 as in FIG. 1.
FIG. 4 illustrates the Tanner graph of the parity check matrix H in FIG. 3.
Herein, in FIG. 4, the check node is represented by plus “+” and the variable node is represented by equal “=”. The check node and the variable node correspond to the row and the column of the parity check matrix H, respectively. A connection between the check node and the variable node is the edge, which corresponds to the element “1” of the parity check matrix.
That is to say, when a j-th row i-th column element of the parity check matrix is 1, in FIG. 4, an i-th variable node (node of “=”) from the top and a j-th check node (node of “+”) from the top are connected to each other by the edge. The edge indicates that the code bit corresponding to the variable node has a constraint condition corresponding to the check node.
In a sum product algorithm being the decoding method of the LDPC code, the variable node operation and the check node operation are repeatedly performed.
FIG. 5 illustrates the variable node operation performed in the variable node.
In the variable node, the message vi corresponding to the edge to be calculated is obtained by the variable node operation in equation (1) using the messages u1 and u2 from other edges connected to the variable node and the received value u01. The message corresponding to another edge is similarly obtained.
FIG. 6 illustrates the check node operation performed in the check node.
Herein, the check node operation in equation (2) may be rewritten as equation (6) using relationship of an equation a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b). Sign(x) is 1 when x≥0 is satisfied and −1 when x<0 is satisfied.
      [          Equation      ⁢                          ⁢      6        ]                                                                                            u                  j                                =                                  2                  ⁢                                                            tanh                                              -                        1                                                              ⁡                                          (                                                                        Π                                                      i                            =                            1                                                                                                              d                              o                                                        -                            1                                                                          ⁢                                                  tanh                          ⁡                                                      (                                                                                          v                                i                                                            2                                                        )                                                                                              )                                                                                                                                              =                                  2                  ⁢                                                            tanh                                              -                        1                                                              ⁡                                          [                                              exp                        ⁢                                                  {                                                                                    ∑                                                              i                                =                                1                                                                                                                              d                                  o                                                                -                                1                                                                                      ⁢                                                                                                                  ⁢                                                          ln                              ⁡                                                              (                                                                  |                                                                      tanh                                    ⁡                                                                          (                                                                                                                        v                                          i                                                                                2                                                                            )                                                                                                        |                                                                )                                                                                                              }                                                ×                                                  Π                                                      i                            =                            1                                                                                                              d                              o                                                        -                            1                                                                          ⁢                        sign                        ⁢                                                  (                                                      tanh                            ⁡                                                          (                                                                                                v                                  i                                                                2                                                            )                                                                                )                                                                    ]                                                                                                                                              =                                  2                  ⁢                                                            tanh                                              -                        1                                                              ⁡                                          [                                              exp                        ⁢                                                  {                                                      -                                                          (                                                                                                ∑                                                                      i                                    =                                    1                                                                                                                                              d                                      o                                                                        -                                    1                                                                                                  ⁢                                                                                                                                  ⁢                                                                  -                                                                      ln                                    ⁡                                                                          (                                                                              tanh                                        ⁡                                                                                  (                                                                                                                                    |                                                                                              v                                                i                                                                                            |                                                                                        2                                                                                    )                                                                                                                    )                                                                                                                                                                  )                                                                                }                                                                    ]                                                        ×                                      Π                                          i                      =                      1                                                                                      d                        o                                            -                      1                                                        ⁢                                      sign                    ⁡                                          (                                              v                        i                                            )                                                                                                                                (          6          )                    
When a function ϕ(x) is defined by an equation ϕ(x)=ln(tan h(x/2)) when x≥0 is satisfied, an equation ϕ−1(x)=2 tan h−1(e−x) is satisfied, so that equation (6) may be deformed to equation (7).
      [          Equation      ⁢                          ⁢      7        ]                                            u            j                    =                                                    ϕ                                  -                  1                                            ⁡                              (                                                      ∑                                          i                      =                      1                                                                                      d                        o                                            -                      1                                                        ⁢                                                                          ⁢                                      ϕ                    ⁡                                          (                                              |                                                  v                          i                                                |                                            )                                                                      )                                      ×                          Π                              i                =                1                                                              d                  o                                -                1                                      ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                          (          7          )                    
In the check node, the check node operation in equation (2) is performed according to equation (7).
That is to say, in the check node, the message uj corresponding to the edge to be calculated is obtained by the check node operation in equation (7) using messages v1, v2, v3, v4, and v5 from other edges connected to the check node as illustrated in FIG. 6. The message corresponding to another edge is similarly obtained.
Meanwhile, the function ϕ(x) in equation (7) may be represented by an equation ϕ(x)=ln((ex+1)/(ex−1)) and ϕ(x)=ϕ−1(x) when x>0 is satisfied. When the functions ϕ(x) and ϕ−1(x) are implemented in hardware, there is a case in which they are implemented using LUT (look up table), and the same LUT is used for both of them.